package algorithm.leetcode;

import algorithm.templates.ListNode;

public class NO21_合并两个有序链表 {

    class PerformanceSolution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);
            ListNode tail = dummy;

            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    tail.next = l1;
                    l1 = l1.next;
                } else {
                    tail.next = l2;
                    l2 = l2.next;
                }
                tail = tail.next;
            }
            tail.next = l1 != null ? l2 : l1;
            return dummy.next;
        }
    }

    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode head = null, next = null;
            int value;

            while (l1 != null || l2 != null) {
                int temp1 = l1 == null ? Integer.MAX_VALUE : l1.val;
                int temp2 = l2 == null ? Integer.MAX_VALUE : l2.val;

                if (temp1 <= temp2) {
                    l1 = l1.next;
                    value = temp1;
                } else {
                    l2 = l2.next;
                    value = temp2;
                }

                if (head == null) {
                    head = new ListNode(value);
                    next = head;
                } else {
                    next.next = new ListNode(value);
                    next = next.next;
                }
                next.next = null;
            }
            return head;
        }
    }
}
